1584. Random shuffle
You are given a
permutation A of length n.
Consider the
following random shuffling procedure applied to the initial array {1, 2, …, n}.
For i = 1, 2, …, n, the following operation is performed
in order:
·
an index r is chosen
uniformly at random from 1 to n;
·
the elements at positions i and r are swapped.
All choices of r are independent. Therefore, there are exactly nn equally likely sequences of random choices.
Determine the
probability that after performing all operations, the resulting array is A.
Input. Each line represents a
separate test. It contains an integer n (1 ≤ n ≤ 10), followed by the elements of array À – a permutation of
numbers from 1 to n.
Output. For each test, print the required probability in a separate
line. The answer must contain at least 6 digits after the decimal point.
|
Sample
input |
Sample
output |
|
1 1 2 1 2 5 4 2 5 1 3 |
1.00000000 0.50000000 0.00672000 |
SOLUTION
probability
Algorithm analysis
Initially, we have the
array{1, 2, …, n}. Then a shuffling procedure
is performed. We are given the final permutation A. We need to find the
probability that this exact permutation is obtained after the procedure.
The required probability
is equal to:
At each step of
the shuffle, a number r is chosen. There are n possible choices
for r. The number of
shuffling steps is also n. Therefore, there are nn possible
sequences of choices. Note that different sequences of choices may lead to the
same final permutation, because nn is much larger
than n!.
Let us store the sequence {1, 2, …, n} in the array cur. We’ll iterate over all
possible choices (r1, r2, …, rn), simulating in cur every possible shuffling
process (1
≤ ri ≤ n). Note that a fixed sequence of
numbers r1, r2, …, rn uniquely
determines which swaps are performed at each step, and therefore also
determines the final array after the procedure is completed. If, after applying
all swaps, we obtain the array A, we count the attempt as successful.
Let the number of such successful attempts be s. Then the required
probability is equal to
s / nn
Let’s implement the shuffle function, which
recursively enumerates all possible continuations of the shuffling process and
counts how many of them lead to the target permutation À.
The function has one
parameter pos, the index of the current iteration (starting from 0). This
means that the first pos swaps have already been performed, and the
array cur stores the state obtained after these operations.
To fit within the time
limit, apply the following pruning. Suppose we are at iteration pos, and
the current array cur differs from the target array A in diff
positions. There are n – pos swaps left to perform. Note that a
single swap can place at most two elements into their correct positions.
Therefore, over the remaining steps we can fix no more than 2 * (n – pos)
positions in total.
If diff > 2 * (n
– pos), then it is already impossible to transform cur into A. In this case, continuing
the search makes no sense, and the current branch of the recursion can be
terminated immediately.
Algorithm implementation
Let us declare the following arrays:
·
a – the given permutation À;
·
cur – the current permutation during the enumeration;
int a[10], cur[10];
The shuffle function recursively enumerates
all possible continuations of the shuffling process, counting how many of them
lead to the target permutation A.
void shuffle(int pos)
{
After all n operations have been performed, it
remains to check whether the obtained array cur matches the required
permutation 
.
If it does, then we have found another successful scenario. In this case, increment
countGood.
if (pos ==
n)
{
for (int i =
0; i < n; i++)
if
(cur[i] != a[i]) return;
countGood++;
return;
}
In the variable diff, count the number of positions
where the current array cur differs from the required permutation A.
int diff
= 0;
for (int i =
0; i < n; i++)
if
(cur[i] != a[i]) diff++;
At this point, we still have n – pos steps
left to perform. A single swap can fix at most two incorrect positions. If the
number of differences already exceeds what can possibly be fixed, then
continuing the recursion is pointless.
So we simply stop exploring this branch of the search.
if
(diff > 2 * (n - pos)) return;
Iterate over all possible values of r.
for (int r =
0; r < n; r++)
{
swap(cur[pos],
cur[r]);
shuffle(pos +
1);
swap(cur[pos],
cur[r]);
}
}
The main part of the program. Read the number n – the size of array À.
while (scanf("%d", &n) == 1)
{
Read the input array À. The
simulation always starts with the array {1, 2, …, n}, which we store in cur.
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
cur[i] = i + 1;
}
Start the enumeration. The variable countGood
counts how many sequences of random choices lead to the array A.
countGood = 0;
shuffle(0);
Compute and print the result.
res = countGood / pow(n, n);
printf("%.6lf\n", res);
}